package 剑指offer;

import 抽象数据类型.ListNode;
import 抽象数据类型.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @description:
 * @author: ywk
 * @date: 2020-10-15
 */
public class 二叉树三种遍历 {
    public static void main(String[] args) {
        System.out.println(upper_bound_(5, 4, new int[]{3, 3, 4, 4, 4,5}));
                TreeNode treeNode = new TreeNode(1);
        treeNode.setLeft(new TreeNode(2));
        treeNode.setRight(new TreeNode(3));

        System.out.println(threeOrders(treeNode).toString());
    }

    /**
     * 二分查找
     *
     * @param n int整型 数组长度
     * @param v int整型 查找值
     * @param a int整型一维数组 有序数组
     * @return int整型
     */
    public static int upper_bound_(int n, int v, int[] a) {
        // write code here

        return find(0, a.length - 1, v, a);
    }

    public static int find(int left, int right, int v, int[] a) {
        int index = a.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (a[mid] >= v) {
                index = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return index + 1;

    }

    public boolean hasCycle(ListNode head) {
        ListNode root = head;
        ListNode temp1 = root;
        ListNode temp2 = root;
        if (root == null) {
            return false;
        }
        while (temp1.next != null && temp2.next != null && temp2.next.next != null) {
            temp1 = temp1.next;
            temp2 = temp2.next.next;
            if (temp1 == temp2) {
                return true;
            }
        }
        return false;
    }
    /**
     *
     * @param root TreeNode类 the root of binary tree
     * @return int整型二维数组
     */
    public static int[][] threeOrders (TreeNode root) {
        // write code here
        TreeNode left = root.left;
        TreeNode right = root.right;

        List<Object> list1 = new ArrayList<>();
        List<Object> list2 = new ArrayList<>();
        List<Object> list3 = new ArrayList<>();
        TreeNode root1 = new TreeNode(root.val);
        root1.left = left;
        root1.right = right;

        TreeNode root2 = new TreeNode(root.val);
        root2.left = left;
        root2.right = right;

        TreeNode root3 = new TreeNode(root.val);
        root3.left = left;
        root3.right = right;

        pre(root1, list1);
        mid(root2, list2);
        back(root3, list3);
        int[][] arr = new int[3][list1.size()];
        for (int i = 0; i < arr.length; i++) {
            if (i == 0) {
                int[] ints = arr[i];
                for (int i1 = 0; i1 < ints.length; i1++) {
                    ints[i1] = (Integer) list1.get(i1);
                }
            }
            if (i == 1) {
                int[] ints = arr[i];
                for (int i1 = 0; i1 < ints.length; i1++) {
                    ints[i1] = (Integer) list2.get(i1);
                }
            }
            if (i == 2) {
                int[] ints = arr[i];
                for (int i1 = 0; i1 < ints.length; i1++) {
                    ints[i1] = (Integer) list3.get(i1);
                }
            }

        }
        return arr;
    }

    public static void pre(TreeNode root, List<Object> list) {
        if (root != null) {
            list.add(root.val);
            pre(root.left, list);
            pre(root.right, list);
        }

    }
    public static void mid(TreeNode root, List<Object> list) {
        if (root != null) {

            mid(root.left, list);
            list.add(root.val);
            mid(root.right, list);
        }
    }
    public static  void back(TreeNode root, List<Object> list) {
        if (root != null) {
            back(root.left, list);
            back(root.right, list);
            list.add(root.val);
        }

    }
}
